package LeetCode1;

import java.util.*;

/**
 * 前K个高频单词 本题还涉及到
 * 如果次数相同，则需要按字母顺序排出。方法为s1.compareTo(s2)
 * 不相同则按照从大到小输出 反转数组方法：Collections.reverse(数组名);
 * 取大用小
 * @author 是阿秋啊
 * @date 2022/03/16 16:35
 **/
public class Num692 {
    //创建自定义类存储不重复单词和出现次数
    private class Words implements Comparable<Words>{
        String s;
        int times;

        public Words(String s, int times) {
            this.s = s;
            this.times = times;
        }

        @Override
        public int compareTo(Words o) {
            //出现次数相同，则按字母排序
            return this.times == o.times ? o.s.compareTo(this.s) : this.times - o.times;
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        //1.遍历单词数组，将不重复单词和出现次数存储在Map集合中
        Map<String,Integer> map = new HashMap<>();
        for (String i : words) {
            map.put(i,map.getOrDefault(i,0) + 1);
        }
        //2.遍历map，创建优先队列，将前k个高频单词入队
        Queue<Words> queue = new PriorityQueue<>();
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.offer(new Words(entry.getKey(),entry.getValue()));
            } else {
                Words temp = queue.peek();
                if (entry.getValue() >= temp.times) {
                    queue.offer(new Words(entry.getKey(),entry.getValue()));
                    queue.poll();
                }
            }
        }
        //此时优先队列中为前k个高频单词
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ret.add(queue.poll().s);
        }
        Collections.reverse(ret);
        return ret;
    }
}
